/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年05月25日
*   描    述：
*   Copyright (C) 2019 All rights reserved.
*   
================================================================*/


#include <iostream>
#include <vector>
#include <math.h>
#include <stdlib.h>

using namespace std;

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if( m == 0 )
            return 0;
        int n = matrix[0].size();
        int maxdp = 0;
        
        int** dp = new int*[m];
        for(int i = 0; i < m; i++){
            dp[i] = new int[n];
            memset(dp[i], 0, sizeof(int)*n);
        }
        for(int i = m - 1; i >= 0; i--){
            if(matrix[i][n-1] == '1'){
                dp[i][n-1] = 1;
                maxdp = 1;
            }else{
                dp[i][n-1] = 0;
            }
        }
        for(int j = n -1; j >= 0; j--){
            if(matrix[m-1][j] == '1'){
                dp[m-1][j] = 1;
                maxdp = 1;
            }else{
                dp[m-1][j] = 0;
            }
        }
        
        int rightarea = 0, bottonarea = 0, rbarea = 0;
        int arg = 0;
        for(int i = m-2; i>= 0; i--){
            for(int j = n - 2; j >= 0; j--){
                if(matrix[i][j] == '1'){
                    rightarea = matrix[i][j+1] == '0'? 0:dp[i][j+1];
                    bottonarea = matrix[i+1][j] == '0'? 0:dp[i+1][j];
                    rbarea = matrix[i+1][j+1] == '0'? 0:dp[i+1][j+1];
                    dp[i][j] = min(min(rightarea, bottonarea), rbarea)+1;
                    maxdp = max(maxdp, dp[i][j]);
                } 
            }
        }
        
        for(int i = m-1; i >= 0; i--)
            delete[] dp[i];
        delete[] dp;

        return maxdp*maxdp;
    }
    
};
